# private
class node():
    def __init__(self, char):
        self.char = char
        self.sons = []
        self.count = 0

def build_tree(words):
    root = node("*")
    count = 1
    cur = root
    for word in words:
        for char in word:
            for son in cur.sons:
                if char == son.char:
                    cur = son
                    break
            else:
                new_node = node(char)
                cur.sons.append(new_node)
                cur = new_node
        # 我很惊奇地发现原始数据里面居然有重复地单词
        if(cur.count == 0):
            cur.count = count
            # print("building: ", word, ": ", count)
            count += 1
        cur = root
    return root

# public
def build_tree_from_file(filename):
    with open(filename, "r") as file:
        # print("打开", filename, "文件")
        words = [line.strip() for line in file.readlines()]
        return build_tree(words)

def get_count(word, root):
    cur = root
    for char in word:
        for son in cur.sons:
            if char == son.char:
                cur = son
                break
        else:
            return -1
    return cur.count

# 测试
if(__name__ == '__main__'):
    words = [
        "son",
        "alibaba",
        "apple",
        "sonic"
    ]

    root = build_tree(words)

    tests = [
        "son",
        "apple",
        "alibaba",
        "sonic",
        "kala",
        "bala"
    ]

    for word in tests:
        print(word, ": ", get_count(word, root))

    pass
